package data_structur.BinaryTree;

import lombok.Data;
import sun.reflect.generics.tree.Tree;

public class BinaryTree {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1, "node1");
        TreeNode node2 = new TreeNode(2, "node2");
        TreeNode node3 = new TreeNode(3, "node3");
        TreeNode node4 = new TreeNode(4, "node4");
        TreeNode node5 = new TreeNode(5, "node5");
        TreeNode node6 = new TreeNode(6, "node6");
        TreeNode node7 = new TreeNode(7, "node7");
        TreeNode node8 = new TreeNode(8, "node8");
        TreeNode node9 = new TreeNode(9, "node9");
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node4.setLeft(node6);
        node3.setRight(node7);
        node7.setLeft(node8);
        node7.setRight(node9);
        //       1
        //    2     3
        //  4   5     7
        //6         8   9
        System.out.println("preOrder:");
        node1.preOrder();// 1 2 4 6 5 3 7 8 9
        System.out.println("midOrder:");
        node1.midOrder();// 6 4 2 5 1 3 8 7 9
        System.out.println("postOrder:");
        node1.postOrder();// 6 4 5 2 8 9 7 3 1

        System.out.println("前序搜索：");
        System.out.println(node1.searchPreOder(1));
        System.out.println(node1.searchPreOder(2));
        System.out.println(node1.searchPreOder(3));
        System.out.println(node1.searchPreOder(4));
        System.out.println(node1.searchPreOder(5));
        System.out.println(node1.searchPreOder(6));
        System.out.println(node1.searchPreOder(7));
        System.out.println(node1.searchPreOder(8));
        System.out.println(node1.searchPreOder(9));
        System.out.println(node1.searchPreOder(10));
    }
}

@Data
class TreeNode {
    private int no;
    private String name;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    // 前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    // 中序遍历
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    // 后序遍历
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    // 前序搜索：
    // （1）首先拿当根节点的no和当前比较，如果相等，则直接返回。
    // （2）如果不相等，则左递归前序查找。
    // （3）如果左递归找到了结果，直接返回，如果找不到，则开始右递归前序查找。
    // （4）如果右递归找到则返回，没找到则返回空。
    public TreeNode searchPreOder(int no) {
        if (this.no == no) {
            return this;
        }
        TreeNode t = null;
        if (this.left != null) {
            t = this.left.searchPreOder(no);
        }
        if (t != null) {
            return t;
        }
        if (this.right != null) {
            t = this.right.searchPreOder(no);
        }
        return t;
    }
}
